#include <iostream>
using namespace std;

/*数据结构定义*/
//二叉树
typedef char ElemType;
typedef struct BiNode{
    ElemType data;
    struct BiNode *left;
    struct BiNode *right;
    struct BiNode *parent;
    int level;
}BiNode,*BiTree;

/*构建*/
#define MAX 20
BiNode *createByLevelOrderListAndInOrderList(
        ElemType levelOrderList[], int levelStart, int levelEnd,
        ElemType inOrderList[],int inStart,int inEnd){
    if (levelStart > levelEnd || inStart > inEnd) return NULL;
    //1.创建根节点
    BiNode *node = (BiNode *)malloc(sizeof(BiNode));
    node->data = levelOrderList[levelStart];
    //2.添加左右子树
    //2.1 确定根节点在中序中的位置
    int rootIndex;
    for(rootIndex = inStart; rootIndex <= inEnd; rootIndex++){
        if(inOrderList[rootIndex] == levelOrderList[levelStart])
            break;
    }
    //2.2 在层次序列中找到子树节点，生成两个新的子树层次序列
    /*用最最暴力的方法搜索出来*/
    ElemType leftLevelList [MAX] = {};
    ElemType rightLevelList [MAX] = {};
    int leftCur = 0;
    int rightCur = 0;
    for (int i = levelStart+1; i <= levelEnd; ++i) {
        for (int j = inStart; j <= rootIndex-1; ++j) {
            if(levelOrderList[i] == inOrderList[j]){
                leftLevelList[leftCur++] = levelOrderList[i];
            }
        }
        for (int j = rootIndex+1; j <= inEnd; ++j) {
            if(levelOrderList[i] == inOrderList[j]){
                rightLevelList[rightCur++] = levelOrderList[i];
            }
        }
    }
    //2.3 构建子树
    node->left = createByLevelOrderListAndInOrderList(
            leftLevelList,0,leftCur - 1,
            inOrderList,inStart,rootIndex -1);
    node->right = createByLevelOrderListAndInOrderList(
            rightLevelList,0,rightCur - 1,
            inOrderList,rootIndex + 1,inEnd);
    //3.返回根节点
    return node;
}



/*冲刺课核心算法：层次法 + 路径法*/

//模拟卷2
//打印到根节点距离最远的节点到根节点的路径（不止一个）
//1.修改数据结构，添加路径和层次索引；（一定要写）
//2.编写代码；
int maxLevel = 0;
BiNode *maxLevelNodes[MAX] = {0};//记录最大层的节点
int maxNum = 0;//最大层节点数量
void preOrder1(BiTree tree,BiNode *parent,int level){
    if(!tree) return ;
    //线索化、层次化
    tree->parent = parent;
    tree->level = level;
    if (maxLevel < tree->level) {
        maxLevel = tree->level;
        maxLevelNodes[0] = tree;
        maxNum = 1;
    } else if (maxLevel == tree->level){
        maxLevelNodes[maxNum++] = tree;
    }
    preOrder1(tree->left,tree,level+1);
    preOrder1(tree->right,tree,level+1);
}
void getLongestPath2Root(BiTree tree){
    preOrder1(tree,NULL,1);
    for (int i = 0; i < maxNum; ++i) {
        BiNode *leaf = maxLevelNodes[i];
        while (leaf){
            printf("%c ",leaf->data);
            leaf = leaf->parent;
        }
        printf("\n");
    }
}

//模拟卷3
//打印二叉树中距离最远的两个节点的路径
/*算法思路：
 *       距离最远的两个节点一定分布在某个子树的左右子树的底部；
 *       而这棵子树左右子树的深度之和是最大的；
 *       找到子树根之后再去找他左右子树最大层次的节点；
 *       最后拼接打印路径；*/

//获取树的深度
int getDepth(BiTree tree){
    if(!tree) return 0;
    int left = getDepth(tree->left);
    int right = getDepth(tree->right);
    return max(left,right) + 1;
}

//先序遍历二叉树，并对他进行线索化、层次化
int maxLong = 0;
void preOrder2(BiTree tree,BiNode *parent,int level,BiTree &root){
    //root为目标子树，使用引用传入
    if (!tree) return ;
    tree->parent = parent;
    tree->level = level;
    //更新目标子树
    int leftDepth = getDepth(tree->left);
    int rightDepth = getDepth(tree->right);
    int sumDepth = leftDepth + rightDepth;
    if(maxLong < sumDepth) {
        maxLong = sumDepth;
        root = tree;
    }
    preOrder2(tree->left,tree,level+1,root);
    preOrder2(tree->right,tree,level+1,root);
}

void preOrder3(BiTree tree,BiNode *&leaf){
    if(!tree) return;
    if (NULL == leaf || tree->level > leaf->level){
        //说明进到下一层了
        leaf = tree;
    }
    preOrder3(tree->left,leaf);
    preOrder3(tree->left,leaf);
}

void getLongestPath(BiTree tree){
    //线索化、层次化，顺便找一下目标子树
    BiTree root = NULL;
    preOrder2(tree,NULL,1,root);
    //搜索目标子树的两个子树的最大层次的节点
    BiNode *left = NULL;
    BiNode *right = NULL;
    preOrder3(root->left,left);
    preOrder3(root->right,right);
    //拼接打印路径
    root->parent = NULL;
    //1.顺序打印左子的路径
    BiNode *p = left;
    while(p->parent){
        printf("%c ",p->data);
        p = p->parent;
    }
    //2.打印根节点
    printf("%c ",root->data);
    //3.逆置打印右子树
    BiNode *stack[MAX] = {0};
    int len = 0;
    p = right;
    while(p->parent){
        stack[len++] = p;
        p = p->parent;
    }
    while(len>0){
        printf("%c ",stack[len-1]->data);
        len--;
    }
    printf("\n");
}


int main(){

    //先序和中序构建二叉树
    char inOrder[] = {'D', 'H', 'B', 'I', 'E', 'A', 'J','F','C','G'};
    char levelOrder[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G','H','I','J'};
    //构建二叉树
    BiTree tree = createByLevelOrderListAndInOrderList(
            levelOrder,0,9,
            inOrder,0,9);

//    getLongestPath2Root(tree);
    getLongestPath(tree);

    return 0;
}